#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    int dx[4] = { 1, -1, 0, 0 };
    int dy[4] = { 0, 0, 1, -1 };
    int countPath(vector<vector<int> >& CityMap, int n, int m) {
        int x, y, xitem, yitem;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (CityMap[i][j] == 1) x = i, y = j;
                else if (CityMap[i][j] == 2) xitem = i, yitem = j;

        vector<vector<int>> dist(n, vector<int>(m, -1)), cnt(n, vector<int>(m, 0));
        dist[x][y] = 0, cnt[x][y] = 1;
        queue<pair<int, int>> q;
        q.push({ x, y });
        while (q.size())
        {
            int num = q.size();
            while (num--)
            {
                auto [i, j] = q.front();
                q.pop();
                for (int k = 0; k < 4; k++)
                {
                    int a = i + dx[k], b = j + dy[k];
                    if (a >= 0 && a < n && b >= 0 && b < m && CityMap[a][b] != -1)
                    {
                        if (dist[a][b] == -1)
                        {
                            dist[a][b] = dist[i][j] + 1;
                            cnt[a][b] += cnt[i][j];
                            q.push({ a, b });
                        }
                        else if (dist[a][b] == dist[i][j] + 1) cnt[a][b] += cnt[i][j];
                    }
                }
            }
        }
        return cnt[xitem][yitem];
    }
};